package com.problem.dynamicProgramming;

/**
 * @author yyh
 * @date 2024年11月14日 上午10:11
 * <a href="https://leetcode.cn/problems/climbing-stairs/?envType=study-plan-v2&envId=top-interview-150">...</a>
 */
public class ClimbStairs {
    //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    //每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    //
    //示例 1：
    //输入：n = 2
    //输出：2
    //解释：有两种方法可以爬到楼顶。
    //1. 1 阶 + 1 阶
    //2. 2 阶

    //示例 2：
    //输入：n = 3
    //输出：3
    //解释：有三种方法可以爬到楼顶。
    //1. 1 阶 + 1 阶 + 1 阶
    //2. 1 阶 + 2 阶
    //3. 2 阶 + 1 阶
    //
    //提示：
    //1 <= n <= 45

    public int climbStairs(int n) {
        int n1 = 1;
        int n2 = 2;

        //1 <= n <= 45
        int[] arr = new int[45];

        //f(n) = f(n-1) + f(n-2)
        if (n == 1) {
            return n1;
        } else if (n == n2) {
            return n2;
        } else if (arr[n - 1] > 0) {
            return arr[n - 1];
        } else {
            arr[n-1] =climbStairs(n - 1) + climbStairs(n - 2);
            return  arr[n-1];
        }
    }

    public int climbStairs1(int n) {
        //f(n) = f(n-1) + f(n-2)
//        if (n == 1) {
//            return 1;
//        } else if (n == 2) {
//            return 2;
//        }

        //f(n-2)
        int p = 0;
        // f(n-1)
        int q= 1;
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = p +q;
            p = q;
            q = res;
        }

        return res;
    }

    public static void main(String[] args) {
        ClimbStairs main = new ClimbStairs();
        System.out.println(main.climbStairs1(1));
        System.out.println(main.climbStairs1(2));
        System.out.println(main.climbStairs1(3));
        System.out.println(main.climbStairs1(4));
        System.out.println(main.climbStairs1(5));
    }

    //f(n) = f(n-1) + f(n-2)
    //可以这么理解，首先确认清楚目的地：
    //目的地1：青蛙在只剩一个台阶到达终点
    //目的地2：青蛙在只剩两个台阶到达终点
    //到达 目的地1 的路线数，我们记做 f(n−1)；
    //到达 目的地2 的路线数，我们记做 f(n−2)；
    //因为两个目的地不同，所以 f(n−1) 绝对不包含 f(n−2)，即不重复。（一开始我就是这里没想通）
    //
    //接下来分析, 从上面两个目的地 到达 终点 的路线数:
    //
    //目的地1 到达 终点 的路线数，只能有一个选择，即跳一个台阶，所以只能是 f(n−1)∗1 ，注意不是+1，这里我们求的是路线数。
    //
    //目的地2 到达 终点 的路线数，这里有两个选择，即跳一个一个台阶跳 或 一次跳两个台阶，但是我们发现如果选择一个一个台阶跳，会经过上面的目的地1，即重复路线，所以我们也只能有一个选择，即一次跳两个台阶，这时，目的地2 到达 终点 的路线数是 f(n−2)∗1，注意不是+1，这里我们求的是路线数。
    //
    //最后：由于一次跳一个台阶或者两个台阶的限制，所以达到终点的前一步，只能可能是从上面两个目的地出发。即得出到达终点的路线数为f(n)=f(n−1)+f(n−2)。
    //
    //发散一下：
    //明白上面的逻辑之后，你就可以知道，如果这只青蛙一次可以跳1个台阶 或 2个台阶 或 3个台阶的时候，公式怎么写了，如下： f(n)=f(n−1)+f(n−2)+f(n−3)
}
